package PenTest.A4x;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Ax {
    /*1. 多点共线问题
        在二维平面上有N点坐标如下：
        （x1,y1）
        （x2,y2）
           ...
        （xn,yn）
        其中任意第i个点的坐标值符合：
         - 1,000,000 < xi < 1,000,000
         - 1,000,000 < yi < 1,000,000
        为了简便所有 x，y 均为整数。
        N 的量级 10,000,000（千万级别）
        求上述N点中最多多少个点在同一条直线上？
        给出解决方法和代码（语言不限）。*/
    //任取其中两个点，计算其表达式y=ax+b，然后遍历整个集合，判断有多少个点在该直线上。

    //任取其中两个点，计算其表达式y=ax+b,判断表达式相等的个数
    public static int countInLine(List<Integer[]> list) {
        int ans=0;
        //记录每个表达式的个数
        Map<String, Integer> map = new HashMap<>();
        List<String> ansList = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                ansList.add(cal(list.get(i), list.get(j)));
            }
        }
        for (String s : ansList) {
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        int maxVal = Integer.MIN_VALUE;
        for (String s : map.keySet()) {
            if (map.get(s) > maxVal) {
                maxVal = map.get(s);
            }
        }
        return maxVal==1?maxVal+1:maxVal;
    }

    //计算y=ax+b表达式
    private static String cal(Integer[] array1,Integer[] array2){
        //计算a:y2-y1/x2-x1
        int a=(array2[1]-array1[1])/(array2[0]-array1[0]);
        //精度损失
        //计算b:
        int b=array2[1]-a*array2[0];
        //唯一确定key
        return Integer.toString(a)+Integer.toString(b);
    }

}
